import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-05-15
 * Time: 10:32
 */
/*给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择
任意 一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半过的数继续执行操作）
请你返回将 nums 数组和 至少 减少一半的 最少 操作数。*/
public class halveArray {
    public static int halveArray(int[] nums) {
        PriorityQueue<Double> heap = new PriorityQueue<>((a, b) -> b.compareTo(a));
        double sum = 0.0;
        for(int x : nums) // 把元素都丢进堆中，并求出累加和
        {
            heap.offer((double)x);
            sum += x;
        }
        sum /= 2.0; // 先算出⽬标和
        int count = 0;
        while(sum > 0) // 依次取出堆顶元素减半，直到减到之前的⼀半以下
        {
            double t = heap.poll() / 2.0;
            sum -= t;
            count++;
            heap.offer(t);
        }
        return count;

    }
    public static void main(String[] args) {
        System.out.println(halveArray(new int[]{5, 19, 8, 1}));
    }
}
